#include "def.h"


/*
v: 求编号为v的顶点到其它点的最短路径。
path: 路径存放在path数组中。 path[i] 存放 到i的前驱结点编号, path[3] = 1 表示： 顶点3是从1过来的
*/

void Dijkstra(Graph &G,int v,int path[])
{
    int dist[MaxSize];//  v到j的路径长度
    int s[MaxSize];// 已找到最短路径的点的集合
    bool Final[MaxSize];//Final[w]=1表示求得顶点V0至Vw的最短路径
    // 初始化dist\path: path[i] 存放 到i的前驱结点编号, -1表示没有
    for (int i = 0; i < G.vertexNum; i++)
    {
        Final[i] = false;
        dist[i] = G.arcs[v][i];
        if (dist[i] != INF){
            path[i] = v;
        }
        else{
            path[i]=-1;
        }
    }
    s[0] = v; // 初始化s
    Final[v] = true;
    int num = 1;
    while (num < G.vertexNum)
    {
        // 在dist中查找最小值元素
        int k = 0,min= INF;
        for (int i = 0; i < G.vertexNum; i++)
        {
            if (i == v)continue;
            if (!Final[i] && dist[i] < min)
            {
                k = i;
                min = dist[i];
            }                
        }
        s[num++] = k;// 将新生成的结点加入集合s
        Final[k] = true;
        // 修改dist和path数组
        for (int i = 0; i < G.vertexNum; i++)
        {
            if (!Final[i] && dist[i] > dist[k] + G.arcs[k][i])
            {
                dist[i] = dist[k] + G.arcs[k][i];
                path[i] = k;
            }
        }
    }
}
